package com.ken.algorithms.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainCD188</li>
 * <li>Description: TODO </li>
 * </ul>
 * @author 程序员ken
 * @date 2021/5/20 0020 上午 11:21
 */
public class MainCD188 {



    /**
     *【题目链接】：https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
     * NowCoder：CD188. 单调栈结构 (进阶)
     *
     * 【题目描述】：
     *  这个题目和上个题目解题思路基本一致，整体的框架都是一样的。
     *  不过由于重复值的存在，我们的栈需要存储的就不是一个一个的数了，
     *  而是一个一个的 List，把值相同的元素放在同一个 List 里面。
     * 【解题思路】：
     *
     * 这个题目和上个题目解题思路基本一致，整体的框架都是一样的。
     * 不过由于重复值的存在，我们的栈需要存储的就不是一个一个的数了，而是一个一个的 List，把值相同的元素放在同一个 List 里面。
     */
    public static void main(String[] args) {
        int [] arr ={3,4,4,5,6,5,7};
        int[][] leftRightMin = findLeftRightMin(arr);

        for (int i = 0; i < leftRightMin.length; i++) {
            System.out.println(Arrays.toString(leftRightMin[i]));
        }
    }


    private static int[][] findLeftRightMin(int[] arr) {
        int[][] res = new int[arr.length][2];
        for (int i = 0; i < res.length; i++) {
            res[i][0] =-1;
            res[i][1] =-1;
        }

        //只能通过 75%，考虑是否数据量太大后 IO 交互太频繁，稍作修改一下，使用 StringBuilder 存储结果，然后做一次输出结果，100% 通过，nice！
        Stack<List<Integer>> stack = new Stack<List<Integer>>();

        int cur = 0;
        boolean fz = false;

        List<Integer> list = null;

        for (int i = 0; i <arr.length ; i++) {
            // 记住 这样 处理 是 针对单调递增的栈
            // 后面的数 小于 前面的数
            // 这样处理栈 遇到后面的值小于栈顶的值 栈顶被移除  此时 栈顶的值可能是后面某个值左侧 最近的比自身小的值 这样 他们两就不能对比(左侧不能对比)
            // 如果不加上arr[stack.peek()] >= arr[i]  保证不了 单调递增性 因为违反了这个条件  栈顶的数据就会出栈  剩下的数据肯定是单调递增的
            while (!stack.isEmpty() && arr[stack.peek().get(0)] >= arr[i]){
                list = stack.pop();
                int leftRight = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);// 取决于列表中最晚加入的那个
                int rigthInd = i;
                        //list.get(list.size()-1);
                for (int j = 0; j <list.size() ; j++) {
                    res[list.get(j)][0] = leftRight;
                    res[list.get(j)][1] = rigthInd;
                }

            }


            //栈里面存着相同元素
            //  stack.peek()!=null &&
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){
                stack.peek().add(i);
            }else{
                list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }

        // 如果不处理这些 剩下的单调递增的数据  就没有处理
        while (!stack.isEmpty()){
            list = stack.pop();
            int leftRight = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for (int j = 0; j <list.size() ; j++) {
                res[list.get(j)][0] = leftRight;
            }
        }
        return res;

    }


}
